无监督构建词库：更快更好的新词发现算法

作者丨苏剑林

单位丨追一科技

研究方向丨NLP，神经网络

个人主页丨kexue.fm

新词发现是 NLP 的基础任务之一，主要是希望通过无监督发掘一些语言特征（主要是统计特征），来判断一批语料中哪些字符片段可能是一个新词。

“新词发现”是一个比较通俗的叫法，更准确的叫法应该是“无监督构建词库”，因为原则上它能完整地构建一个词库出来，而不仅仅是“新词”。当然，你可以将它跟常用词库进行对比，删掉常见词，就可以得到新词了。

分词的目的

分词一般作为文本挖掘的第一步，仿佛是很自然的，但事实上也应该问个为什么：为什么要分词？人本来就是按照字来书写和理解的呀？

当模型的记忆和拟合能力足够强（或者简单点，足够智能）的时候，我们完全可以不用分词的，直接基于字的模型就可以做，比如基于字的文本分类、问答系统等，早已有人在研究。但是，即便这些模型能够成功，也会因为模型复杂而导致效率下降，因此，很多时候（尤其是生产环境中），我们会寻求更简单、更高效的方案。

什么方案最高效？以文本分类为例，估计最简单高效的方案就是“朴素贝叶斯分类器”了，类似的，比较现代的是 FastText，它可以看作是“朴素贝叶斯”的“神经网络版”。要注意，朴素贝叶斯基于一个朴素的假设：特征之间相互独立。这个假设越成立，朴素贝叶斯的效果就越好。然而，对于文本来说，显然上下文紧密联系，这个假设还成立吗？

注意到，当特征之间明显不独立的时候，可以考虑将特征组合之后，使得特征之间的相关性减弱，再用朴素贝叶斯。比如，对于文本，如果以字为特征，则朴素假设显然不成立，如“我喜欢数学”中的“喜”和“欢”、“数”和“学”都明显相关，这时候我们可以考虑将特征进行组合，得到“我/喜欢/数学”，这样三个片段之间的相关性就没有那么强了，因此可以考虑用上述结果。

可以发现，这个过程很像分词，或者反过来说，分词的主要目的之一，就是将句子分为若干个相关性比较弱的部分，便于进一步处理。从这个角度来看，分的可能不一定是“词”，也可能是短语、常用搭配等。

说白了，分词就是为了削弱相关性，降低对词序的依赖，这一点，哪怕在深度学习模型中，都是相当重要的。有些模型，不分词但是用 CNN，也就是把若干个字组合作为特征来看，这也是通过字的组合来减弱特征间的相关性的体现。

算法大意

既然分词是为了削弱相关性，那么我们分词，就是在相关性弱的地方切断了。文章《【中文分词系列】 2. 基于切分的新词发现》[1] 其实就是这个意思，只是那里认为，文本的相关性仅由相邻两字（2grams）来决定，这在很多时候都是不合理的，比如“林心如”中的“心如”、“共和国”中的“和国”，凝固度（相关性）都不是很强，容易错切。

因此，本文就是在前文的基础上改进，那里只考虑了相邻字的凝固度，这里同时考虑多字的内部的凝固度（ngrams），比如，定义三字的字符串内部凝固度为：

这个定义其实也就是说，要枚举所有可能的切法，因为一个词应该是处处都很“结实”的，4 字或以上的字符串凝固度类似定义。一般地，我们只需要考虑到 4 字（4grams）就好（但是注意，我们依旧是可以切出 4 字以上的词来的）。

考虑了多字后，我们可以设置比较高的凝固度阈值，同时防止诸如“共和国”之类的词不会被切错，因为考虑三字凝固度，“共和国”就显得相当结实了，所以，这一步就是“宁放过，勿切错”的原则。

但是，“各项”和“项目”这两个词，它们的内部凝固度都很大，因为前面一步是“宁放过，勿切错”，因此这样会导致“各项目”也成词，类似的例子还有“支撑着”、“球队员”、“珠海港”等很多例子。但这些案例在 3grams 中来看，凝固度是很低的，所以，我们要有一个“回溯”的过程，在前述步骤得到词表后，再过滤一遍词表，过滤的规则就是，如果里边的 n 字词，不在原来的高凝固度的 ngrams 中，那么就得“出局”。

所以，考虑 ngrams 的好处就是，可以较大的互信息阈值情况下，不错切词，同时又排除模凌两可的词。就比如“共和国”，三字互信息很强，两字就很弱了（主要还是因为“和国”不够结实），但是又能保证像“的情况”这种不会被切出来，因为阈值大一点，“的情”和“的情况”都不结实了。

详细的算法

完整的算法步骤如下：

第一步，统计：选取某个固定的 n，统计 2grams、3grams、…、ngrams，计算它们的内部凝固度，只保留高于某个阈值的片段，构成一个集合 G；这一步，可以为 2grams、3grams、…、ngrams 设置不同的阈值，不一定要相同，因为字数越大，一般来说统计就越不充分，越有可能偏高，所以字数越大，阈值要越高；

第二步，切分：用上述 grams 对语料进行切分（粗糙的分词），并统计频率。切分的规则是，只有一个片段出现在前一步得到的集合 G 中，这个片段就不切分，比如“各项目”，只要“各项”和“项目”都在 G 中，这时候就算“各项目”不在 G 中，那么“各项目”还是不切分，保留下来；

第三步，回溯：经过第二步，“各项目”会被切出来（因为第二步保证宁放过，不切错）。回溯就是检查，如果它是一个小于等于 n 字的词，那么检测它在不在 G 中，不在就出局；如果它是一个大于 n 字的词，那个检测它每个 n 字片段是不是在 G 中，只要有一个片段不在，就出局。还是以“各项目”为例，回溯就是看看，“各项目”在不在 3gram中，不在的话，就得出局。

每一步的补充说明：

1. 较高的凝固度，但综合考虑多字，是为了更准，比如两字的“共和”不会出现在高凝固度集合中，所以会切开（比如“我一共和三个人去玩”，“共和”就切开了），但三字“共和国”出现在高凝固度集合中，所以“中华人民共和国”的“共和”不会切开；

2. 第二步就是根据第一步筛选出来的集合，对句子进行切分（你可以理解为粗糙的分词），然后把“粗糙的分词结果”做统计，注意现在是统计分词结果，跟第一步的凝固度集合筛选没有交集，我们认为虽然这样的分词比较粗糙，但高频的部分还是靠谱的，所以筛选出高频部分；

3. 第三步，例如因为“各项”和“项目”都出现高凝固度的片段中，所以第二步我们也不会把“各项目”切开，但我们不希望“各项目”成词，因为“各”跟“项目”的凝固度不高（“各”跟“项”的凝固度高，不代表“各”跟“项目”的凝固度高），所以通过回溯，把“各项目”移除（只需要看一下“各项目”在不在原来统计的高凝固度集合中即可，所以这步计算量是很小的）。

代码实现

本次开源地址位于：https://github.com/bojone/word-discovery
注意这个脚本应该只能在 Linux 系统下使用。如果你想要在 Windows 下使用，应该需要做些修改，具体做哪些修改，我也不知道，请自行解决。注意算法本身理论上能适用于任意语言，但本文的实现原则上只适用于以“字”为基本单位的语言。
Github 中核心的脚本是 word_discovery.py [2]，它包含了完整的实现和使用例子。下面我们简单梳理一下这个例子。
首先，写一个语料的生成器，逐句返回语料：

import pymongo
import re

db = pymongo.MongoClient().baike.items

# 语料生成器，并且初步预处理语料
# 这个生成器例子的具体含义不重要，只需要知道它就是逐句地把文本yield出来就行了
def text_generator():
    for d in db.find().limit(5000000):
        yield re.sub(u'[^\u4e00-\u9fa50-9a-zA-Z ]+', '\n', d['text'])

读者不需要看懂我这个生成器究竟在做什么，只需要知道这个生成器就是在逐句地把原始语料给 yield 出来就行了。如果你还不懂生成器怎么写，请自己去学。请不要在此文章内讨论“语料格式应该是怎样的”、“我要怎么改才能适用我的语料”这样的问题，谢谢。
顺便提一下，因为是无监督训练，语料一般都是越大越好，几百 M 到几个 G 都可以，但其实如果你只要几 M 的语料（比如一部小说），也可以直接测试，也能看到基本的效果（但可能要修改下面的参数）。
有了生成器之后，配置一些参数，然后就可以逐个步骤执行了：

min_count = 32
order = 4
corpus_file = 'wx.corpus' # 语料保存的文件名
vocab_file = 'wx.chars' # 字符集
ngram_file = 'wx.ngrams' # ngram集
output_file = 'wx.vocab' # 最后导出的词表


write_corpus(text_generator(), corpus_file) # 将语料转存为文本
count_ngrams(corpus_file, order, vocab_file, ngram_file) # 用Kenlm统计ngram
ngrams = KenlmNgrams(vocab_file, ngram_file, order, min_count) # 加载ngram
ngrams = filter_ngrams(ngrams.ngrams, ngrams.total, [0, 1, 3, 5]) # 过滤ngram

注意，kenlm 需要一个以空格分词的、纯文本格式的语料作为输入，而 write_corpus 函数就是帮我们做这件事情的，然后 count_ngrams 就是调用 kenlm 的 count_ngrams 程序来统计 ngram。所以，你需要自行编译好 kenlm，并把它的 count_ngrams 放到跟 word_discovery.py 同一目录下。如果有 Linux 环境，那 kenlm 的编译相当简单，笔者之前在这里 [3] 也讨论过 kenlm，可以参考。
 count_ngrams 执行完毕后，结果会保存在一个二进制文件中，而 KenlmNgrams 就是读取这个文件的，如果你输入的语料比较大，那么这一步会需要比较大的内存。最后 filter_ngrams 就是过滤 ngram 了，[0, 1, 3, 5] 是互信息的阈值，其中第一个 0 无意义，仅填充用，而 1、3、5 分别是 2gram、3gram、4gram 的互信息阈值，基本上单调递增比较好。 
至此，我们完成了所有的“准备工作”，现在可以着手构建词库了。首先构建一个 ngram 的 Trie 树，然后用这个 Trie 树就可以做一个基本的“预分词”：

ngtrie = SimpleTrie() # 构建ngram的Trie树

for w in Progress(ngrams, 100000, desc=u'build ngram trie'):
    _ = ngtrie.add_word(w)

candidates = {} # 得到候选词
for t in Progress(text_generator(), 1000, desc='discovering words'):
    for w in ngtrie.tokenize(t): # 预分词
        candidates[w] = candidates.get(w, 0) + 1

这个预分词的过程在上文中已经介绍过了，总之有点像最大匹配，由 ngram 片段连接成尽可能长的候选词。最后，再把候选词过滤一下，就可以把词库保存下来了：

# 频数过滤
candidates = {i: j for i, j in candidates.items() if j >= min_count}
# 互信息过滤(回溯)
candidates = filter_vocab(candidates, ngrams, order)

# 输出结果文件
with open(output_file, 'w') as f:
    for i, j in sorted(candidates.items(), key=lambda s: -s[1]):
        s = '%s\t%s\n' % (i.encode('utf-8'), j)
        f.write(s)

评测

这是我从 500 万篇微信公众号文章（保存为文本之后是 20 多 G）提取出来的词库，供读者有需使用。

https://kexue.fm/usr/uploads/2019/09/1023754363.zip

训练时间好像是五六个小时吧，我记不是很清楚了，总之比原始的实现会快，资源消耗也低一些。 
读者之前老说我写的这些算法没有标准评测，这次我就做了一个简单的评测，评测脚本是 evaluate.py。

https://github.com/bojone/word-discovery/blob/master/evaluate.py

具体来说，提取刚才的词典 wx.vocab.zip 的前 10 万个词作为词库，用结巴分词加载这个10万词的词库（不用它自带的词库，并且关闭新词发现功能），这就构成了一个基于无监督词库的分词工具，然后用这个分词工具去分 bakeoff 2005 [4] 提供的测试集，并且还是用它的测试脚本评测，最终在 PKU 这个测试集上得分是：

也就是说能做到 0.746 的 F1。这是个什么水平呢？ICLR 2019 有一篇文章叫做 Unsupervised Word Discovery with Segmental Neural Language Models [5]，里边提到了它在同一个测试集上的结果为 F1=0.731，照这样看这个算法的结果还不差于顶会的最优结果呢。
注：这里是为了给效果提供一个直观感知，比较可能是不公平的，因为我不确定这篇论文中的训练集用了哪些语料。但我感觉在相同时间内本文算法会优于论文的算法，因为直觉论文的算法训练起来会很慢。作者也没有开源，所以有不少不确定之处，如有错谬，请读者指正。

总结

本文复现了笔者之前提出了新词发现（词库构建）算法，主要是做了速度上的优化，然后做了做简单的效果评测。但具体效果读者还是得在使用中慢慢调试了。 

祝大家使用愉快，Enjoy it！

相关链接

[1] https://kexue.fm/archives/3913[2] https://github.com/bojone/word-discovery/blob/master/word_discovery.py[3] https://kexue.fm/archives/3956#实践：训练[4] http://sighan.cs.uchicago.edu/bakeoff2005/[5] https://arxiv.org/abs/1811.09353

点击以下标题查看作者其他文章： 

#投 稿 通 道#

 让你的论文被更多人看到 

如何才能让更多的优质内容以更短路径到达读者群体，缩短读者寻找优质内容的成本呢？答案就是：你不认识的人。

总有一些你不认识的人，知道你想知道的东西。PaperWeekly 或许可以成为一座桥梁，促使不同背景、不同方向的学者和学术灵感相互碰撞，迸发出更多的可能性。

PaperWeekly 鼓励高校实验室或个人，在我们的平台上分享各类优质内容，可以是最新论文解读，也可以是学习心得或技术干货。我们的目的只有一个，让知识真正流动起来。

📝 来稿标准：

• 稿件确系个人原创作品，来稿需注明作者个人信息（姓名+学校/工作单位+学历/职位+研究方向） 

• 如果文章并非首发，请在投稿时提醒并附上所有已发布链接 

• PaperWeekly 默认每篇文章都是首发，均会添加“原创”标志

📬 投稿邮箱：

• 投稿邮箱：[e-mail] 

• 所有文章配图，请单独在附件中发送 

• 请留下即时联系方式（微信或手机），以便我们在编辑发布时和作者沟通

🔍

现在，在「知乎」也能找到我们了

进入知乎首页搜索「PaperWeekly」

点击「关注」订阅我们的专栏吧

关于PaperWeekly

PaperWeekly 是一个推荐、解读、讨论、报道人工智能前沿论文成果的学术平台。如果你研究或从事 AI 领域，欢迎在公众号后台点击「交流群」，小助手将把你带入 PaperWeekly 的交流群里。

▽ 点击 | 阅读原文 | 查看作者博客